// https://leetcode.cn/problems/max-points-on-a-line/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        
        if (n <= 2) {
            return n;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            unordered_map<int, int> mp;

            for (int j = i + 1; j < n; j++) {
                int deltaX = points[j][0] - x;
                int deltaY = points[j][1] - y;
                int gcdNum = gcd(deltaX, deltaY);
                int k = myHash(deltaX / gcdNum, deltaY / gcdNum);

                if (mp.count(k)) {
                    mp[k]++;
                } else {
                    mp[k] = 1;
                }
            }

            for (auto it = mp.begin(); it != mp.end(); it++) {
                ans = max(ans, it->second + 1);
            }
        }
        return ans;
    }

    int myHash(int x, int y) {
        return x + y * 10001;
    }

    int gcd(int x, int y) {
        return y ? gcd(y, x % y) : x;
    }
};
